In conventional computerized design tools, such as computer aided design (CAD) systems, solid modeling techniques can be employed for designing physical objects such as parts and tools. Solid modeling allows three dimensional (3-D) complex solids to be formed from operations involving simpler objects. For example, a cube object and a cylinder object can be combined by subtracting the cylinder from the cube to create a complex cubic object having a cylindrical hole. Some conventional solid modeling applications use history tree-based functionality (e.g., constructive solid geometry, CSG) for creating complex solids. A history tree embodies the construction history of a complex solid and can be represented as an n-ary tree having operators for inner nodes and simple objects for leaf nodes. A complex cubic object having a cylindrical hole, for instance, could be represented in a history tree having two leaf nodes (i.e., a cube object and a cylinder object), and a parent subtraction operator node.
Along with the construction history of a complex solid, the shape, position and orientation of each object forming the complex solid can be specified in a history tree. A CAD system can use a history tree to create a presentation of a complex solid by evaluating the history tree (e.g., traversing the tree in a bottom-up fashion and applying the operators along the way). Moreover, a CAD system can automatically create and modify history trees to reflect users' manipulations and modifications of visually rendered or “presented” objects, and to update the presentation of the objects. For example, a user can interactively change the position of a visual representation of a handle object to a new location on a visual representation of a cup object (e.g., by dragging the handle using a mouse). This will cause the CAD system that the user is interacting with to update the position and orientation data in the handle leaf node in the history tree of the complex cup solid and update the presentation of the complex cup solid. While the user is in the process of dragging the handle object, the CAD system can provide continuous feedback by updating the visual presentation of the resulting complex cup solid on every mouse move so that the users can observe how the dragging is affecting the resulting complex cup solid.
Evaluating a history tree can introduce latencies in updating presentations of complex solids (e.g., due to the time it can take to evaluate a history tree for a complex solid having many parts). The latency and delay in presenting an updated image can be a distraction for users interactively manipulating complex solids using a CAD system. For example, a complex solid model of an automobile engine may be represented by a history tree containing hundreds of nodes. If a user interactively moves a single part of the engine to a different location, the entire history tree may be required to be reevaluated many times during the move creating a less than desirable user experience.